package myself.a004QuickSor;

import java.util.Arrays;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/22
 * Time 19:51
 * Mail 739153436@qq.com
 */
public class DutchFlag {
    public static void main(String[] args) {
        DutchFlag dutchFlag = new DutchFlag();
        int[] arr = {1, 2, 3, 4, 5, 4, 3, 2, 1, 3};
        int[] result = dutchFlag.netherlandsFlag(arr, 0, arr.length - 1);
        Arrays.stream(result).forEach(value -> System.out.println(value));
        System.out.println();
        Arrays.stream(arr).forEach(value -> System.out.println(value));

    }

    // 以 r 下标的元素作为分割值将数组切成两半
    public static int partition(int[] arr, int l, int r) {
        // 两个指针，后面这个指针见到小的就往前面扔，并且把前面大的拖过来
        if (l == r) {
            return l;
        }
        if (l > r) {
            return -1;
        }

        // 总是指向分割点的前一个
        int lp = l - 1;
        // 总是指向末尾
        int rp = l;

        while (rp < r) {
            if (arr[rp] <= arr[r]) {
                swap(arr, ++lp, rp);
            }
            rp++;
        }
        swap(arr, ++lp, r);
        return lp;
    }

    // arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
    // <arr[R] ==arr[R] > arr[R]
    public static int[] netherlandsFlag(int[] arr, int l, int r) {
        if (l == r) {
            return new int[]{l, r};
        }
        if (l > r) {
            return new int[]{-1, -1};
        }
        int lp = l - 1;
        int rp = r;
        int midp = l;
        // 为什么是中间指针和右指针相等的时候就结束循环呢，理解如下：
        // 因为 rp 右指针在第一次移动之后永远指向的都是 >arr[R] 的数字，因为只要中间指针碰撞到了大数，那么就会移动到后面，并且后面的指针会指向已知的大数
        // 所以一旦两个指针相撞，我们前面得出的结论就是 rp 指向的一定是大数，所以相撞之后两个指针同时指向我们的大数，就可以和最后一位进行位置的交换
        while (midp < rp) {
            if (arr[midp] == arr[r]) {
                midp++;
            } else if (arr[midp] > arr[r]) {
                swap(arr, midp, --rp);
            } else {
                swap(arr, midp++, ++lp);
            }
        }
        swap(arr, midp, r);
        // 这里的边界都是包含 == 的数
        return new int[]{lp + 1, midp};
    }

    public static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}
